#ifndef CS240_LINKED_LIST_H
#define CS240_LINKED_LIST_H

#include <string>
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
using namespace std;

template <typename S> class LinkedList;

//! LLNode implements a doubly-linked list node
template <typename T>
class LLNode {
		friend class LinkedList<T>;  //!< LinkedList can access private members of LLNode
	public:
	
		//!  Constructor
		LLNode(const T & v, LLNode<T> * p, LLNode<T> * n) :
		  value(v), prev(p), next(n){
		}
		
		//! Copy Constructor 
		LLNode(const LLNode<T> & other) :
		   value(other.value),prev(other.prev),next(other.next){
		}
	
		//!  Read-only public methods for use by clients of the LinkedList class
		const T & GetValue() const{
		  return value;
		}
	
	
		LLNode<T> * GetPrevious()const{
		  return prev;
		}
	
	
		LLNode<T> * GetNext()const{
		  return next;
		}
		
		//! Assignment operator 
		LLNode<T> & operator=(const LLNode<T> & other){
			if(this!=&other){
				value=other.value;
				prev=other.prev;
				next=other.next;
			}
			return *this;
		}
	
	private:
		void DeepDelete(){
			if(next!=NULL){
				next->DeepDelete();
				delete next;
			}
		}
		
		T value;        //!< value stored in the node
		LLNode<T> * prev;            //!< pointer to previous node in the list
		LLNode<T> * next;            //!< pointer to next node in the list
};


//! LinkedList implements a doubly-linked list
template <typename L>
class LinkedList{
	public:
	
			LinkedList(){
				top=NULL;
				last=NULL;
				size=0;
			}

			LinkedList(const LinkedList<L> & other){
				if (other.top==NULL){
					top=NULL;
					last=NULL;
					size= 0;
				}
				else{
					top = new LLNode<L>(other.top->value,NULL,NULL);
					LLNode<L> *copy = other.top->next;
					last = top;
					while (copy!=NULL){
						LLNode<L> *temp=new LLNode<L>(copy->value,last,NULL);
						last->next=temp;
						last=temp;
						copy= copy->next;
					}
				size= other.size;
				}
			}

			~LinkedList(){
				if (top!=NULL)
					top->DeepDelete();
				delete top;
				top=NULL;
				last=NULL;
			}

			LinkedList<L>& operator =(const LinkedList<L> & other){
				if (this != &other){
					if (top!=NULL){
						top->DeepDelete();
						delete top;
						top=NULL;
						last=NULL;
					}
					if (other.top==NULL){
						top=NULL;
						last=NULL;
						size= 0;
					}
					else{
						top = new LLNode<L>(other.top->value,NULL,NULL);
						LLNode<L> *copy = other.top->next;
						last = top;
						while (copy!=NULL){
							LLNode<L> *temp=new LLNode<L>(copy->value,last,NULL);
							last->next=temp;
							last=temp;
							copy= copy->next;
						}
					size= other.size;
					}
				}
				return *this;
			}

			bool IsEmpty() const{
				if (size==0)
					return true;
				return false;
			}

			void Clear(){
				if (top!=NULL){
					top->DeepDelete();
					delete top;
					top=NULL;
					last=NULL;
				}
				size=0;
			}

			int GetSize() const{
				return size;
			}

			L* Get(int index){
				if (index>size-1)
					return NULL;
				else{
					LLNode<L> *cur=top;
					for (int i =0; i<index; i++)
						cur=cur->next;
					return &(cur->value);
				}

			}

			LLNode<L> * GetFirst()const{
				return top;
			}

			LLNode<L> * GetLast()const{
				return last;
			}

			LLNode<L> * Insert(const L & v){	//add to back
				Insert(v, GetLast());
			}

			LLNode<L> * Insert(const L & v, LLNode<L> * n){
				LLNode<L> *temp;
				if (n==NULL){
					if (top==NULL){				//First added
						temp= new LLNode<L>(v,NULL,NULL); //HERE
						top=temp;
						last=temp;
					}
					else{						//Add to Front
						temp=new LLNode<L>(v,NULL,top); //HERE
						top->prev=temp;
						top=temp;
					}
				}
				else{
					if (n==last){					//Add to Back
						temp= new LLNode<L>(v,last,NULL);
						last->next=temp;
						last=temp;
					}
					else{						//Add to Middle
						temp= new LLNode<L>(v,n,n->next);
						n->next->prev=temp;
						n->next=temp;
					}
				}
				size++;
				return temp;
			}

			L * Find(const L & v, LLNode<L> * n) const{
				LLNode<L> *cur;
				if (top==NULL)
					return NULL;

				if(n==NULL)
					cur=top;
				else
					cur=n->next;
				while(cur!=NULL){
					if (cur->value.compare(v)==0)
						return &(cur->value);
					cur= cur->next;
				}
				return NULL;
			}

			bool contains(const L &v){
				//TODO FIND IT!
				return false;
			}

			void Remove(LLNode<L> * n){
				LLNode<L> *cur;
				if (top!=NULL){
					cur=top;
					while(cur!=NULL){
						if (cur==n){
							if (cur!=top)
								cur->prev->next=cur->next;
							else{
								top=top->next;
							}
							if (cur!=last)
								cur->next->prev=cur->prev;
							else
								last=last->prev;
							size--;
							delete cur;
							break;
						}
						cur=cur->next;
					}
				}
			}

			void Print(){
				if (size==0)
					cout <<"empty";
				else{
					LLNode<L> *cur = top;
					while (cur!=NULL){
						cout << cur->value << endl;
						cur = cur->next;
					}
				}
			}
	
	private:
		LLNode<L> * top;
		LLNode<L> *last;
		int size;

};


#endif

